package com.leetcode.dynamic_programming;

/**
 * @author Dennis Li
 * @date 2020/9/8 18:56
 */
public class MaxProduct_152 {

    public static void main(String[] args) {
        MaxProduct_152 ans = new MaxProduct_152();

        int[] nums = {2, 3, -2, 4};

        System.out.println(ans.maxProduct(nums));

    }

    public int maxProduct(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }

        int len = nums.length;

        int[][] dp = new int[len][len];

        int max = Integer.MIN_VALUE;

        for (int i = 0; i < len; i++) {
            dp[i][i] = nums[i];
            max = Math.max(max, nums[i]);
        }

        for (int i = 0; i < len; i++) {
            for (int j = i + 1; j < len; j++) {
                dp[i][j] = Integer.MIN_VALUE;

                int product1 = dp[i + 1][j] * nums[i];
                int product2 = dp[i][j - 1] * nums[j];
                int product3 = dp[i + 1][j - 1] * nums[i] * nums[j];

                if (product1 >= dp[i + 1][j]) {
                    dp[i][j] = Math.max(product1, dp[i][j]);
                }

                if (product2 >= dp[i][j - 1]) {
                    dp[i][j] = Math.max(product2, dp[i][j]);
                }

                if (product3 >= dp[i + 1][j - 1]) {
                    dp[i][j] = Math.max(product3, dp[i][j]);
                }

                max = Math.max(max, dp[i][j]);
            }
        }

        return max;
    }

    class Solution {
        // 状态方程，以i结尾的最大值
        public int maxProduct(int[] nums) {
            int max = Integer.MIN_VALUE, imax = 1, imin = 1;
            for (int num : nums) {
                if (num < 0) {
                    int tmp = imax;
                    imax = imin;
                    imin = tmp;
                }

                // 记录当前连续数组的最大最小值
                // 如果更小，那么就变为num，相当于做了数组的截断
                imax = Math.max(imax * num, num);
                imin = Math.min(imin * num, num);

                max = Math.max(max, imax);
            }
            return max;
        }
    }

    public int max(int... nums) {
        int max = Integer.MIN_VALUE;
        for (int num : nums) {
            max = Math.max(num, max);
        }
        return max;
    }

}
